package com.gitee.wsl.collections.map

import kotlin.math.round


class ArrayHashMap<K, V> :  MutableMap<K, V> {

    class MapEntry<K, V>(override var key: K, override var value: V, var hash: Int) : MutableMap.MutableEntry<K, V> {

        var deleted: Boolean = false

        override fun setValue(newValue: V): V {
            val old = this.value
            this.value = newValue
            return old
        }
    }

    override val entries: MutableSet<MutableMap.MutableEntry<K, V>>
        get() {
            val entrySet: MutableSet<MutableMap.MutableEntry<K, V>> = mutableSetOf()
            for (i in arrayOfMapEntrys.indices) {
                val entry = arrayOfMapEntrys[i]
                if (entry != null && !entry.deleted ) {
                    entry.value?.let {
                        entrySet.add(entry as MutableMap.MutableEntry<K, V>)
                    }
                }
            }
            return entrySet
        }

    lateinit var arrayOfMapEntrys: Array<MapEntry<K, V?>?>

    init {
        this.clear()
    }

    override fun containsValue(value: V): Boolean {
       return arrayOfMapEntrys.find { it?.value == value }!=null
    }

    override val keys: MutableSet<K>
        get() {
            val entrySet: MutableSet<K> = mutableSetOf()
            for (i in arrayOfMapEntrys.indices) {
                val entry = arrayOfMapEntrys[i]
                if (entry != null && !entry.deleted) {
                    entrySet.add(entry.key)
                }
            }
            return entrySet
        }
    override val values: MutableCollection<V>
        get() {
            val entrySet: MutableSet<V> = mutableSetOf()
            for (i in arrayOfMapEntrys.indices) {
                val entry = arrayOfMapEntrys[i]
                if (entry != null && !entry.deleted ) {
                    entry.value?.let { entrySet.add(it) }
                }
            }
            return entrySet
        }

    override fun isEmpty(): Boolean = arrayOfMapEntrys.isEmpty()

    override fun putAll(from: Map<out K, V>) {
        from.forEach {
            put(it.key,it.value)
        }
    }

    override var size: Int = 0

    private var loadThreshold = 0


    private fun setEntries(entries: Array<MapEntry<K, V?>?>) {
        this.arrayOfMapEntrys = entries
        this.loadThreshold = round(this.arrayOfMapEntrys.size * LOAD_FACTOR).toInt()
    }


    override fun containsKey(key: K): Boolean {
        val table = this.arrayOfMapEntrys

        if (this.isEmpty()) {
            return false
        }

        val hash = hash(key)
        val index = hash and (table.size - 1)
        for (i in index until table.size) {
            val entry = table[i] ?: return false

            if (entry.deleted) {
                if (entry.hash == hash && entry.key == key) {
                    return false
                }
            } else if (entry.hash == hash && entry.key == key) {
                return true
            }
        }
        return false
    }

    override fun get(key: K): V? {
        val table = this.arrayOfMapEntrys

        val hash = hash(key)
        val index = hash and (table.size - 1)
        for (i in index until table.size) {
            val entry = table[i] ?: return null

            if (entry.deleted) {
                if (entry.hash == hash && entry.key == key) {
                    return null
                }
            } else if (entry.hash == hash && entry.key == key) {
                return entry.value
            }
        }
        return null
    }

    override fun clear() {
        this.size = 0
        setEntries(arrayOfNulls<MapEntry<K,V?>?>(8))
    }

    override fun put(key: K, value: V): V? {
        val hash = hash(key)

        var table = this.arrayOfMapEntrys
        while (true) {
            val index = hash and (table.size - 1)
            var tombstone: MapEntry<K, V?>? = null
            for (i in index until table.size) {
                var entry = table[i]
                if (entry != null && !entry.deleted) {
                    if (entry.hash == hash && entry.key == key) {
                        return entry.setValue(value)
                    }
                } else if (entry != null && entry.deleted) {
                    if (tombstone == null) {
                        tombstone = entry
                    }
                } else if (tombstone != null) {
                    size++
                    tombstone.key = key
                    tombstone.hash = hash
                    tombstone.deleted = false
                    resizeIfLoadHigh(table)

                    return tombstone.setValue(value)
                } else {
                    entry = MapEntry(key, value, hash)
                    table[i] = entry
                    size++
                    resizeIfLoadHigh(table)

                    return null
                }
            }

            table = resize(table)
            setEntries(table)
        }
    }

    private fun resizeIfLoadHigh(table: Array<MapEntry<K, V?>?>) {
        if (this.size >= this.loadThreshold) {
            setEntries(this.resize(table))
        }
    }

    private fun resize(table: Array<MapEntry<K, V?>?>): Array<MapEntry<K, V?>?> {
        val newTable = arrayOfNulls<MapEntry<K, V?>?>(table.size * 2)

        for (i in table.indices) {
            val entry = table[i]

            if (entry != null && !entry.deleted) {
                val hash = entry.hash
                val index = hash and (newTable.size - 1)
                var success = false
                for (j in index until newTable.size) {
                    if (newTable[j] == null) {
                        newTable[j] = entry
                        success = true
                        break
                    }
                }
                require(success)
            }
        }
        return newTable
    }


    override fun remove(key: K): V? {
        val table: Array<MapEntry<K, V?>?> = this.arrayOfMapEntrys

        val hash = hash(key)
        val index = hash and (table.size - 1)
        for (i in index until table.size) {
            val entry = table[i] ?: return null

            if (entry.deleted) {
                if (entry.hash == hash && entry.key == key) {
                    return null
                }
            }

            if (entry.hash == hash && entry.key == key) {
                entry.deleted = true
                entry.hash = 0
                size--
                return entry.setValue(null)
            }
        }
        return null
    }


    companion object {
        private const val LOAD_FACTOR = 0.85f

        fun hash(key: Any?): Int {
            var h: Int
            return if ((key == null)) 0 else (key.hashCode().also {
                h = it
            }) xor (h ushr 16)
        }
    }
}